package com.zp.self.module.level_4_算法练习.算法.双指针.快慢指针;

import com.zp.self.module.level_4_算法练习.数据结构.链表.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author By ZengPeng
 */
public class 力扣_141_环形链表 {
    //测试
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        n1.next=n2;
        n2.next=n3;
        n3.next=n4;
        System.out.println(hasCycle2(n1));
    }

    /**
     * 题目：给你一个链表的头节点 head ，判断链表中是否有环。
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
     * 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
     * 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
     * 如果链表中存在环，则返回 true 。 否则，返回 false 。
     *
     * 分析：
     *      1.set存储
     *      #大神的优秀解法 ：使用快慢指针，若指针相遇则判断有环
     *
     * 边界值注意：
     *      1.
     **/
    public static boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();//set存储不能重复出现
        while (head!=null){
            if(set.contains(head))return  true;
            set.add(head);
            head = head.next;
        }
        return  false;
    }
    //使用快慢指针，若指针相遇则判断有环
    // 循环条件：quick!=null
    // 终止条件： slow==quick
    // 单步操作：slow = slow.next   quick每次跳两个位置
    public static boolean hasCycle2(ListNode head) {
        if(head==null || head.next==null) return  false;
        ListNode slow =head,quick =head.next;
        while (quick != null){
            if(slow == quick)return  true;
            if(quick.next==null ) return  false;
            slow = slow.next;
            quick = quick.next.next;
        }
        return  false;
    }
}
